package algorithm;

/**
 * @author maguangqi
 * @version 1.0
 * 122. 买卖股票的最佳时机 II
 * https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/
 * 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
 * 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
 * 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）
 * 输入: [7,1,5,3,6,4]
 * 输出: 7
 * 这道题考察的是贪心算法,也就是求解问题时,总是做出在当前看来是最好的选择
 * 贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。
 * @date 2020/7/4 22:22
 */
public class Profit122 {
    /**
    *解法: 使用贪心算法解决
    * [7,1,5,3,6,4] -> 7
     * [1,2,3,4,5] ->4
     * 因为题目说可以买卖多次,因此我们可以使用在同一天先卖出再买入或者先买入再卖出
     *
     * 我们只要后一天比当天的数额大,那我们就当天买入,后天卖出.
     * 举例: 7 1 不操作
     *       1 5 | 1买入,5块卖出 赚4块
     *       5 3   不操作
     *       3 6 | 3买入,6卖出 赚3 块
     *       6 4 不操作
     *     共计赚7块
     *  每天都涨的情况
     *  1 2 3 4 5
     *       1 2  1买入,2卖出 赚1块
     *       2 3  2买入,3卖出 赚1块
     *       3 4 3买入,4卖出 赚1块
     *       4 5 4 买入,5卖出 赚1块
     *       共计赚4块
     *
    */
    public int maxProfit(int[] prices) {
        int profit=0;
        for (int i = 0; i < prices.length-1; i++) {
            //只要后一天比当天的数额大,那我们就当天买入,后天卖出.收益就是他们的差值
            //其实就是贪心算法,总是做出在当前看来是最好的选择.
            if (prices[i + 1] > prices[i]) {
                profit += prices[i + 1] - prices[i];
            }
        }
        return profit;
    }

    public static void main(String[] args) {
        Profit122 profit122 = new Profit122();
        int[] i = new int[]{7, 1, 5, 3, 6, 4};
        int[] j = new int[]{1,2,3,4,5};
        int[] h = new int[]{7, 6,5,4,3};
        System.out.println(profit122.maxProfit(i));
        System.out.println(profit122.maxProfit(j));
        System.out.println(profit122.maxProfit(h));
    }
}
